1. Field of the Invention
The present invention relates to data networking and specifically to maintaining forwarding adjacencies in a data network.
2. Background Information
A data network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end stations, such as computers. Many types of network segments are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect nodes, such as personal computers and workstations, over dedicated, private communications links located in the same general physical location, such as a building or a campus. LANs may also connect intermediate nodes, such as routers, that are co-located within a close range.
WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Certain intermediate nodes, such as routers, are often configured to “route” data, such as packets, between various nodes in the network. Routing is typically performed at the network layer or layer-3 (L3) of the Open Systems Interconnect Reference Model (OSI-RM). Routers often maintain forwarding databases (FDBs), which are typically configured to hold routing information including L3 addresses and interface information that the router uses to determine where data (e.g., data packets) are to be forwarded in order to reach their destination. For example, a router may have a routing database containing one or more entries wherein each entry contains a L3 destination address of a destination node and interface information about an interface (e.g., a port) on the router through which the destination node may be reached. A data packet containing a destination address that matches a destination address of an entry in the routing table is forwarded by the router to the interface specified by the matching entry for transfer to the destination node.
In addition, a router may maintain a link-state database (LSDB) which is often configured to hold link-state information about data links in the data network. Here, the router may derive a topology of the network using the link-state information in the LSDB. The router may further use the link-state information along with information contained in advertisement messages (described below) received by the router to determine if the topology of the network has changed.
A router may execute one or more routing protocols that enable the router to route packets and exchange routing and link-state information with other routers in the network. The routers may use this information to, inter alia, configure (e.g., compute) their FDBs and LSDBs. The routing protocols may include link-state protocols, such as the Intermediate-System-to-Intermediate-System (IS-IS) protocol or the Open Shortest Path First (OSPF) protocol. Routing and link-state information is typically exchanged between the routers in the form of advertisement messages. For example, nodes executing the IS-IS protocol exchange routing and link-state information using an advertisement message called a link-state packet. Likewise, nodes executing the OSPF protocol exchange routing and link-state information using an advertisement message called a link-state advertisement (LSA). As used herein, an advertisement message refers generically to a message that an intermediate node uses to convey routing and/or link-state information to other intermediate nodes in the network.
An intermediate node that acquires an advertisement message may use information contained therein to update its FDB and LSDB, and maintain a topology of the network. If the network topology changes (e.g., a link fails), an intermediate node detecting the change usually updates it's FDB and LSDB, and generates one or more advertisement messages that account for the change. The intermediate node may then flood the advertisement messages to its neighboring nodes, thereby triggering a “network convergence.” That is, the neighboring nodes acquire the advertisement messages, update their FDBs and LSDBs based on information contained in the advertisement message and flood the advertisement message to their neighboring nodes and so on. This process may continue until all the intermediate nodes in the network have updated their FDBs and LSDBs and have “converged” on a new network topology that reflects the changed network topology.
Routers may transfer data packets through the network between a source and destination in a “connection-oriented” manner using a connection-oriented protocol. A connection-oriented protocol transfers data packets through the network over a predefined path, often called a connection or circuit, that is established between the source and destination. Here, the connection or circuit is established between the source and destination before any data are transferred. After the connection has been established, data are transferred between the source and destination over a path defined by the connection. When the connection is no longer needed, the connection is typically “torn down” and resources, such as nodes, interfaces, protocols and so on, utilized by the connection are made available for other connections. A resource, as used herein, refers to entities associated with an intermediate node. These entities may include the intermediate node itself, an interface (e.g., a port) on the intermediate node and a protocol running on the intermediate node. An example of a connection-oriented protocol is the Multiprotocol Label Switching (MPLS) protocol. MPLS provides a framework that embodies various features enabled by a connection-oriented link layer including, e.g., Quality of Service (QoS), Traffic Engineering and Constraint-based Routing (CR).
Some connection-oriented protocols utilize unidirectional connections, i.e., connections that transfer data in one direction from a source to a destination. For example, a unidirectional connection between a router A and a router B transfers data in one direction from router A to router B. In order to transfer data in the other direction, i.e., from router B to router A, another unidirectional connection from router B to router A would have to be established. The connections may be “signaled” end-to-end using a signaling protocol, such as the Resource Reservation Protocol (RSVP). The end of the connection that initiates the signaling for the connection is often called the “head-end” of the connection and the end of the connection that terminates the signaling is often called the “tail-end” of the connection. The router hosting the head-end of the connection is often called the head-end node and the router hosting the tail-end of the connection is often called the tail-end node. Thus, for example, in a connection from a source to a destination where router A hosts the “head-end” of the connection and router B hosts the tail-end of the connection, router A is the head-end node and router B is the tail-end node.
To accommodate high availability, some connection-oriented protocols include techniques that enable various links, e.g., in a MPLS label-switched path (MPLS LSP), to be protected from failure by a backup tunnel. For example, P. Pan, et al., “Fast Reroute Extensions to RSVP-TE for LSP Tunnels,” draft-ietf-mpls-rsvp-fastreroute-04.txt, available from the Internet Engineering Task Force (IETF), http)://www.ietf.org describes a MPLS “fast reroute” (FRR) technique that may be used to quickly reroute a set of traffic engineered (TE) MPLS LSPs around a failed “protected” link, shared risk link group (SRLG) or node onto a pre-signaled “backup” tunnel. In a typical arrangement, two MPLS LSP tunnels, i.e., a primary tunnel and the backup tunnel, are created for a link to protect the link. Traffic normally carried by the link is carried on the primary tunnel. If the primary tunnel fails, e.g., due to a failure of a physical link used by the primary tunnel, the backup tunnel carries data traffic destined for the primary tunnel. The backup tunnel acts as a “fast-reroute” for the primary tunnel and obviates having to resort to other perhaps costlier measures, such as tearing down the primary MPLS TE LSP and establishing a new primary MPLS TE LSP around the failed network element.
A MPLS TE LSP may be “announced” as a “link” in an advertisement message in order to make the MPLS TE LSP appear as a single “physical link” to other intermediate nodes in the network even though it may actually span one or more physical links in the network. A MPLS TE LSP advertised in this manner is often called a “forwarding adjacency” (FA). FAs are described in K. Kompella, et al., “LSP Hierarchy with Generalized MPLS TE,” draft-ietf-mpls-lsp-hierarchy-08.txt, available from the IETF. As with other MPLS TE LSPs, a MPLS TE LSP associated with a FA may be protected by employing a protection scheme, such as the MPLS FRR scheme described above. Here, a primary tunnel is established as a FA, wherein the primary tunnel is configured to normally carry traffic and the backup tunnel is configured to carry traffic for the FA should the primary tunnel fail.
An advantage with protected FAs is that the time it takes to “switch over” from the primary tunnel to the backup tunnel is typically on the order of tens of milliseconds and is often seamless to the network. The switchover time is considerably faster than if the intermediate nodes had to converge on a new network topology that takes into account the failure. Further, since the switchover is seamless, a network topology change is not triggered thus, obviating the need for the network to converge on a new network topology which may consume valuable time and potentially cause network outages. In other words, because the primary tunnel is configured as a FA and is protected with a local repair mechanism, such as FRR, the network topology remains unchanged for the other nodes of the network. Indeed, the FA MPLS TE LSP is locally rerouted onto the backup tunnel and is still announced as a physical link in advertisement messages.
A disadvantage with protected FAs is that they are not dynamic. That is, data may be carried on the backup tunnel of a failed FA indefinitely until e.g., the failure is no longer present and the FA's primary tunnel is re-established (recovers). If the backup tunnel of the failed FA follows a less than optimal path, network efficiency and performance may suffer for an unacceptable period of time.